package com.datastructures2.sanlieTable;

import com.datastructures2.背包队列栈.Queue;

/**
 * @author MaoLin Wang
 * @date 2020/3/38:21
 */
public class LinearProbingHashST<Key, Value> {
    private Key[] keys;
    private Value[] values;

    /**
     * 键值对数
     */
    private int N;
    /**
     * 线性表大小
     */
    private int M;

    public LinearProbingHashST(int M) {
        this.M = M;
        keys = (Key[]) new Object[this.M];
        values = (Value[]) new Object[this.M];
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");
        if (value==null){
            delete(key);
        }
        //保证使用率 N/M 不能超过1/2 ，当使用率趋近于1时，探测的次数会变得很大
        if (N>=M/2){
            resize(M*2);
        }
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                values[i] = value;
                return;
            }
        }
        keys[i] = key;
        values[i] = value;
        N++;
    }

    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                return values[i];
            }
        }
        return null;
    }

    public void delete(Key key) {
        if (!contains(key)) {
            return;
        }
        int i=hash(key);
        //线性探测找到待删除的key的索引
        while (!keys[i].equals(key)){
            i=(i+1)%M;
        }
        //置空
        keys[i]=null;
        values[i]=null;
        //将i+1的位置到下一个空位置前的所有key重新插入到散列表中
        i=(i+1)%M;
        while (keys[i]!=null){
            Key oldKey=keys[i];
            Value oldValue=values[i];
            keys[i]=null;
            values[i]=null;

            N--;
            put(oldKey,oldValue);
            i=(i+1)%M;
        }
        N--;
        //数组减小一半，如果N/M 为12.5% 或更少
        if (N>0 && N <= M/8){
            resize(M/2);
        }
    }

    private void resize(int i) {
        LinearProbingHashST<Key,Value>lp=new LinearProbingHashST<>(i);
        for (int j = 0; j < M; j++) {
            if (keys[j]!=null){
                lp.put(keys[i],values[i]);
            }
        }
        keys=lp.keys;
        values=lp.values;
        M=lp.M;
    }

    private boolean contains(Key key) {
        if (key==null){
            return false;
        }
        return get(key)!=null;

    }
    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < M; i++)
            if (keys[i] != null) queue.enqueue(keys[i]);
        return queue;
    }

    public static void main(String[] args) {
        LinearProbingHashST<String,Integer> linearProbingHashST=new LinearProbingHashST<>(16);
        linearProbingHashST.put("S",0);
        linearProbingHashST.put("E",1);
        linearProbingHashST.put("A",2);
        linearProbingHashST.put("R",3);
        linearProbingHashST.put("C",4);
        linearProbingHashST.put("H",5);
        linearProbingHashST.put("E",6);
        linearProbingHashST.put("X",7);
        linearProbingHashST.put("A",8);
        linearProbingHashST.put("M",9);
        linearProbingHashST.put("P",10);
        linearProbingHashST.put("L",11);
        linearProbingHashST.put("E",12);

        linearProbingHashST.delete("C");
    }
}
